package Algorithm.sort;

/**
 * @Desc: 单向扫描划分方式
 * @author: cww
 * @DateTime: 2020-04-13 0:45
 */

public class ForwardScanSort {
    public static void main(String[] args) {
        int[] items = new int[]{4,5,6,6,2,1};
        forwardScanSort(items,0,5);
        System.out.println(items);
    }
    public static void forwardScanSort(int[] items, int start, int end) {
            if (start<end){
                int head = items[start];
                int i = start,j=start+1;
                while (j<=end){
                    if (items[j]<head){
                        swap(items,++i,j);
                    }
                    j++;
                }
                swap(items,start,i);
                forwardScanSort(items, start,i-1);
                forwardScanSort(items, i+1,end);
            }

}


    public static void swap(int[] item, int p, int q){
        int temp = item[p];
        item[p] = item[q];
        item[q] = temp;
    }

    public static void forwardScanSort1(int[] items, int start, int end) {
        if(start<end){
            int head = items[start];
            int i = start,j=start+1;
            while(j<=end){
                if(items[j]<head){
                    swap(items,++i,j);
                }
                j++;
            }
            swap(items,start,i);
            forwardScanSort1(items,start,i-1);
            forwardScanSort1(items,i+1,end);
        }
    }
}
